package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-time-to-reach-destination-in-directed-graph/
 * @create 2025/9/24 18:31
 * @since JDK17
 */

public class Solution28 {
    public int minTime(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for (int[] e : edges) {
            g[e[0]].add(new int[] { e[1], e[2], e[3] });
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        heap.add(new int[] { 0, 0 });
        dis[0] = 0;
        while (!heap.isEmpty()) {
            var p = heap.poll();
            if (p[1] > dis[p[0]]) {
                continue;
            }
            for (var q : g[p[0]]) {
                int u = Math.max(p[1], q[1]);
                if (u <= q[2] && u + 1 < dis[q[0]]) {
                    dis[q[0]] = u + 1;
                    heap.add(new int[] { q[0], u + 1 });
                }
            }
        }

        return dis[n - 1] == Integer.MAX_VALUE ? -1 : dis[n - 1];
    }
}
